package zuoshen_video2.dynamic;

import java.util.Arrays;

import org.junit.Test;

public class RobotWalkInK {
    
    /* 
        机器人走k步到达目的地问题：
        机器人在1 ~ n的格子中行走，每次只能向左或者向右走一格
        问有多少种方案从起始地点s到目的地a(a∈[1, n])
    */

    //1.递归法
    public int dfs(int idx, int cur, int k, int a, int n) {
        if (cur == k) {
            return idx == a ? 1 : 0;
        }
        int left = 0;
        if (idx > 1) {
            left = dfs(idx - 1, cur + 1, k, a, n);
        }
        int right = 0;
        if (idx < n) {
            right = dfs(idx + 1, cur + 1, k, a, n);
        }
        return left + right;
    }


    public int robotPaths1(int n, int k, int a, int s) {
        return dfs(s, 0, k, a, n);
    }

    @Test
    public void test() {
        System.out.println(robotPaths1(5, 4, 4, 2));
    }

        //2.记忆化搜索方法
        /* 
            1. 找改变量：
                idx, cur
            2. 确定范围
                idx[1, n] cur[0, k]
            3. 初始化搜索矩阵
                因为可能存在0，因此初始化为-1
            4. 优化dfs逻辑
        */
        public int dfs2(int idx, int cur, int k, int a, int n) {
            if (p[idx][cur] >= 0) {
                System.out.println("I am used!");
                return p[idx][cur];
            }
            if (cur == k) {
                p[idx][cur] = idx == a ? 1 : 0;
                return p[idx][cur];
            }
            int left = 0;
            if (idx > 1) {
                left = dfs(idx - 1, cur + 1, k, a, n);
            }
            int right = 0;
            if (idx < n) {
                right = dfs(idx + 1, cur + 1, k, a, n);
            }
            p[idx][cur] = left + right;
            return p[idx][cur];
        }
    
        int[][] p;
        public int robotPaths2(int n, int k, int a, int s) {
            p = new int[n + 1][k + 1];
            for (int i = 1; i <= n; i++) {
                Arrays.fill(p[i], -1);
            }
            return dfs2(s, 0, k, a, n);
        }

        @Test
        public void test2() {
            System.out.println(robotPaths2(5, 4, 4, 2));
        }

        public int robotPaths3(int n, int k, int a, int s) {
            if (a < 1 || a > n) return 0;
            int[][] f = new int[n + 1][k + 1];
            //只有f[a][0]才是1，f[!a][0]默认为0 //第二维表示还剩的步数
            f[a][0] = 1;
            //考虑谁依赖谁：因为赋值了f[x][0], 因此必定依赖的是f[x][0], 故必须从纵轴开始考虑
            for (int j = 1; j <= k; j++) {
                for (int i = 1; i <= n; i++) {
                    f[i][j] = 0;
                    if (i > 1) f[i][j] += f[i - 1][j - 1];
                    if (i < n) f[i][j] += f[i + 1][j - 1];
                }
            }
            Arrays.deepToString(f);
            return f[s][a];
        }


        @Test
        public void test3() {
            System.out.println(robotPaths3(5, 4, 4, 2));
        }

}
